package leetcode;

import java.util.*;

/**
 * description:
 * author:张腾
 * date:2021-06-20
 */
public class leetcode1600 {
    class ThroneInheritance {
        Map<String, List<String>> edges;
        Set<String> dead;
        String king;

        public ThroneInheritance(String kingName) {
            edges = new HashMap<String, List<String>>();
            dead = new HashSet<String>();
            king = kingName;
        }

        public void birth(String parentName, String childName) {
            List<String> children = edges.getOrDefault(parentName, new ArrayList<String>());
            children.add(childName);
            edges.put(parentName,children);
        }

        public void death(String name) {
            dead.add(name);
        }

        public List<String> getInheritanceOrder() {
            ArrayList<String> ans = new ArrayList<>();
            preOrder(ans,king);
            return ans;
        }

        public void preOrder(List<String> ans,String name){
            if (!dead.contains(name)) ans.add(name);

            List<String> children = edges.getOrDefault(name, new ArrayList<String>());
            for (String child : children) {
                preOrder(ans,child);
            }
        }
    }
}
